% optimizer_v3_nsga.m
% 基于非支配排序的多目标优化器，寻找时间和Spill的帕累托最优前沿。
function [pareto_front] = optimizer_v3_nsga(initial_schedule, graph, code_map, caps, initial_params, options)
    % ========================================================================
    %                            初始化
    % ========================================================================
    fprintf('--- 开始多目标优化 (optimizer_v_nsga) ---\n');
    
    % --- 1. 预计算祖先矩阵 ---
    fprintf('  优化器 > 正在预计算祖先矩阵...\n');
    num_nodes = graph.num_nodes;
    is_ancestor = false(num_nodes, num_nodes);
    for i = 1:num_nodes
        q = graph.predecessors_list{i};
        visited = false(num_nodes, 1);
        head = 1;
        while head <= length(q)
            curr = q(head); head = head + 1;
            if ~visited(curr)
                visited(curr) = true;
                is_ancestor(curr, i) = true;
                q = [q, graph.predecessors_list{curr}];
            end
        end
    end
    fprintf('  优化器 > 预计算完成。\n');
    
    % --- 2. 初始评估，获取基准分数 ---
    fprintf('  优化器 > 正在对初始解进行"三合一"评估以确立基准...\n');
    [initial_time, initial_spill, initial_best_alloc_strategy, initial_final_params] = evaluate_candidate_three_ways(initial_schedule, initial_params, graph, code_map, caps, []); 
    
    if isinf(initial_time)
        error('优化失败：作为基准的初始解评估超时，无法继续优化。');
    end
    
    initial_scores = struct('time', initial_time, 'spill', max(1, initial_spill));
    fprintf('  优化器 > 基准解 -> 时间: %d, Spill: %d (使用 %s 策略)\n', initial_time, initial_spill, initial_best_alloc_strategy);
    % --- 3. 创建初始种群 ---
    fprintf('  优化器 > 正在创建和评估初始种群...\n');
    population = cell(options.population_size, 1);
    
    population{1} = struct('schedule', initial_schedule, 'params', initial_final_params, 'time', initial_time, 'spill', initial_spill);
    parfor i = 2:options.population_size
        temp_schedule = initial_schedule;
        temp_params = initial_params;
        if rand() < 0.5
            temp_schedule = mutate_schedule(temp_schedule, graph, is_ancestor); 
        else
            temp_params = mutate_params(temp_params, options);
        end
        [t, s, as, p] = evaluate_candidate_three_ways(temp_schedule, temp_params, graph, code_map, caps, initial_scores);
        population{i} = struct('schedule', temp_schedule, 'params', p, 'time', t, 'spill', s);
    end
    population = vertcat(population{:});
    
    % --- 4. 对初始种群进行非支配排序 ---
    [population] = non_dominated_sort(population);
    initial_front1 = population([population.rank] == 1);
    fprintf('  优化器 > 初始种群评估完成，最优前沿有 %d 个解。\n\n', length(initial_front1));
    % ========================================================================
    %                            主迭代循环 (代际进化)
    % ========================================================================
    for gen = 1:options.generations
        fprintf('  优化器 > --- 第 %d/%d 代 ---\n', gen, options.generations);
        
        front1_indices = find([population.rank] == 1);
        parent_indices = front1_indices(randi(length(front1_indices), options.batch_size, 1));
        
        offspring = cell(options.batch_size, 1);
        parfor k = 1:options.batch_size
            parent = population(parent_indices(k));
            
            if rand() < options.schedule_move_prob
                child_schedule = mutate_schedule(parent.schedule, graph, is_ancestor);
                child_params = parent.params;
            else
                child_schedule = parent.schedule;
                child_params = mutate_params(parent.params, options);
            end
            
            [t, s, as, p] = evaluate_candidate_three_ways(child_schedule, child_params, graph, code_map, caps, initial_scores);
            offspring{k} = struct('schedule', child_schedule, 'params', p, 'time', t, 'spill', s);
        end
        offspring = vertcat(offspring{:});
        
        % --- 3. 精英选择：合并父代与子代，并选出下一代 ---
        
        % *** 已修改: 在拼接前，移除 population 中用于排序的临时字段 ***
        temp_population = rmfield(population, {'rank', 'crowding_distance', 'domination_count', 'dominated_solutions'});
        combined_population = [temp_population; offspring];
        
        [sorted_combined_pop] = non_dominated_sort(combined_population);
        
        new_population = [];
        front_num = 1;
        while length(new_population) + length(find([sorted_combined_pop.rank] == front_num)) <= options.population_size
            new_population = [new_population; sorted_combined_pop([sorted_combined_pop.rank] == front_num)];
            front_num = front_num + 1;
        end
        
        if length(new_population) < options.population_size && front_num <= length(unique([sorted_combined_pop.rank]))
            last_front = sorted_combined_pop([sorted_combined_pop.rank] == front_num);
            if ~isempty(last_front)
                [~, idx] = sort([last_front.crowding_distance], 'descend');
                last_front = last_front(idx);
                
                remaining_space = options.population_size - length(new_population);
                new_population = [new_population; last_front(1:min(remaining_space, length(last_front)))];
            end
        end
        
        population = new_population;
        
        current_front1 = population([population.rank] == 1);
        fprintf('  优化器 > 当前最优前沿有 %d 个解。\n', length(current_front1));
    end
    
    pareto_front = population([population.rank] == 1);
    fprintf('--- 多目标优化完成 ---\n');
end
% ========================================================================
%                         内部辅助函数
% ========================================================================
function [best_time, best_spill, best_alloc_strategy, final_params] = evaluate_candidate_three_ways(schedule, spill_params, graph, code_map, caps, initial_scores)
    strategies = {'BestFit', 'LowAddress', 'LifetimeAware'};
    best_time = inf;
    best_spill = inf;
    best_alloc_strategy = 'None';
    
    is_initial_eval = isempty(initial_scores);
    
    for i = 1:length(strategies)
        current_params = spill_params;
        current_params.alloc_strategy = strategies{i};
        graph_copy = graph;
        
        if is_initial_eval
            [time, spill, ~, ~] = evaluate_schedule(schedule, graph_copy, code_map, caps, current_params, []);
        else
            [time, spill, ~, ~] = evaluate_schedule(schedule, graph_copy, code_map, caps, current_params, initial_scores);
        end
        
        if (time < best_time && spill <= best_spill) || (time <= best_time && spill < best_spill)
            best_time = time;
            best_spill = spill;
            best_alloc_strategy = strategies{i};
        elseif time == best_time && spill == best_spill
            best_alloc_strategy = strategies{i};
        end
    end
    final_params = spill_params;
    final_params.alloc_strategy = best_alloc_strategy;
end
function new_schedule = mutate_schedule(schedule, graph, is_ancestor)
    node_idx_to_move = randi(length(schedule));
    node_to_move = schedule(node_idx_to_move);
    ancestors = find(is_ancestor(:, node_to_move));
    descendants = find(is_ancestor(node_to_move, :));
    positions = 1:length(schedule);
    ancestor_pos = positions(ismember(schedule, ancestors));
    latest_ancestor = 0;
    if ~isempty(ancestor_pos), latest_ancestor = max(ancestor_pos); end
    descendant_pos = positions(ismember(schedule, descendants));
    earliest_descendant = length(schedule) + 1;
    if ~isempty(descendant_pos), earliest_descendant = min(descendant_pos); end
    valid_range = (latest_ancestor + 1):(earliest_descendant - 1);
    valid_range(valid_range == node_idx_to_move) = [];
    new_schedule = schedule;
    if ~isempty(valid_range)
        new_pos = valid_range(randi(length(valid_range)));
        new_schedule(node_idx_to_move) = [];
        if new_pos > node_idx_to_move, new_pos = new_pos - 1; end
        new_schedule = [new_schedule(1:new_pos-1); node_to_move; new_schedule(new_pos:end)];
    end
end
function new_params = mutate_params(params, options)
    new_params = params;
    thr_range = options.threshold_range(2) - options.threshold_range(1);
    mutation = (rand() - 0.5) * thr_range * 0.1;
    new_params.min_farthest_use_threshold = new_params.min_farthest_use_threshold + mutation;
    new_params.min_farthest_use_threshold = max(options.threshold_range(1), min(options.threshold_range(2), new_params.min_farthest_use_threshold));
    weights = [new_params.w_use, new_params.w_vol, new_params.w_vic];
    weights = abs(weights + (rand(1,3) - 0.5) * 0.2);
    weights = weights / sum(weights);
    new_params.w_use = weights(1);
    new_params.w_vol = weights(2);
    new_params.w_vic = weights(3);
end
function [population] = non_dominated_sort(population)
    pop_size = length(population);
    for i = 1:pop_size
        population(i).domination_count = 0;
        population(i).dominated_solutions = [];
    end
    fronts = {[]};
    for i = 1:pop_size
        for j = (i+1):pop_size
            p = population(i);
            q = population(j);
            if (p.time < q.time && p.spill <= q.spill) || (p.time <= q.time && p.spill < q.spill)
                population(i).dominated_solutions = [population(i).dominated_solutions, j];
                population(j).domination_count = population(j).domination_count + 1;
            elseif (q.time < p.time && q.spill <= p.spill) || (q.time <= p.time && q.spill < p.spill)
                population(j).dominated_solutions = [population(j).dominated_solutions, i];
                population(i).domination_count = population(i).domination_count + 1;
            end
        end
        if population(i).domination_count == 0
            population(i).rank = 1;
            fronts{1} = [fronts{1}, i];
        end
    end
    front_idx = 1;
    while true 
        if front_idx > length(fronts) || isempty(fronts{front_idx})
            break; 
        end
        next_front = [];
        for i = 1:length(fronts{front_idx})
            p_idx = fronts{front_idx}(i);
            p = population(p_idx);
            for j = 1:length(p.dominated_solutions)
                q_idx = p.dominated_solutions(j);
                population(q_idx).domination_count = population(q_idx).domination_count - 1;
                if population(q_idx).domination_count == 0
                    population(q_idx).rank = front_idx + 1;
                    next_front = [next_front, q_idx];
                end
            end
        end
        if ~isempty(next_front)
            fronts{front_idx + 1} = next_front; 
        end
        front_idx = front_idx + 1;
    end
    for i = 1:pop_size, population(i).crowding_distance = 0; end
    for i = 1:(front_idx-1)
        front_indices = fronts{i};
        if isempty(front_indices) || length(front_indices) < 3, continue; end
        times = [population(front_indices).time];
        spills = [population(front_indices).spill];
        [~, sort_idx_time] = sort(times);
        [~, sort_idx_spill] = sort(spills);
        population(front_indices(sort_idx_time(1))).crowding_distance = inf;
        population(front_indices(sort_idx_time(end))).crowding_distance = inf;
        population(front_indices(sort_idx_spill(1))).crowding_distance = inf;
        population(front_indices(sort_idx_spill(end))).crowding_distance = inf;
        time_range = max(times) - min(times);
        spill_range = max(spills) - min(spills);
        if time_range > 0
            for j = 2:(length(front_indices)-1)
                idx = front_indices(sort_idx_time(j));
                prev_idx = front_indices(sort_idx_time(j-1));
                next_idx = front_indices(sort_idx_time(j+1));
                population(idx).crowding_distance = population(idx).crowding_distance + (population(next_idx).time - population(prev_idx).time) / time_range;
            end
        end
        if spill_range > 0
            for j = 2:(length(front_indices)-1)
                idx = front_indices(sort_idx_spill(j));
                prev_idx = front_indices(sort_idx_spill(j-1));
                next_idx = front_indices(sort_idx_spill(j+1));
                population(idx).crowding_distance = population(idx).crowding_distance + (population(next_idx).spill - population(prev_idx).spill) / spill_range;
            end
        end
    end
end